import java.util.*;

public class Other {
    public int getSum(int a, int b) {
        if(a==0)return b;
        else if(b==0)return a;
        int mov=a%b;
        mov<<=1;
        int noMovSum=a^b;
        return getSum(noMovSum,mov);
    }

    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int len=nums.length;
        int key=nums[0];
        for (int i=0;i<len;i++){
            key=nums[i];
            if(map.containsKey(key)){
                int v=map.get(key)+1;
                if(v>len/2) break;
                map.put(key,v);
            }else {
                map.put(key,1);
            }
        }
        return key;
    }

    public int lengthOfLastWord(String s) {
        String []temp=s.split(" ");
        String last=temp[temp.length-1];
        return last.length();
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> nums=new Stack<>();
        for (int i=0;i<tokens.length;i++){
            if(tokens[i].equals("*")){
                int a=nums.pop();
                int b=nums.pop();
                nums.push(b*a);
            }else if(tokens[i].equals("/")){
                int a=nums.pop();
                int b=nums.pop();
                nums.push(b/a);
            }else if(tokens[i].equals("+")){
                int a=nums.pop();
                int b=nums.pop();
                nums.push(b+a);
            }else if(tokens[i].equals("-")){
                int a=nums.pop();
                int b=nums.pop();
                nums.push(b-a);
            }else {
                int num=Integer.valueOf(tokens[i]);
                nums.push(num);
            }
        }
        return nums.pop();
    }

    public int leastInterval(char[] tasks, int n) {
        int[]data=new int[26];
        for (int i=0;i<tasks.length;i++){
            data[tasks[i]-'A']++;
        }
        Arrays.sort(data);
        int temp=25;
        while (temp>=0&&data[25]==data[temp]){
            temp--;
        }
        return Math.max((data[25]-1)*(n+1)+25-temp,tasks.length);
    }
}
